// 300
package AVL树;


import org.w3c.dom.Node;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.Queue;

public class AVL<E> extends BinarySearchTree<E> {
    public AVL() {
        this(null);
    }

    public AVL(Comparator<E> comparator) {
        super(comparator);
    }

    @Override
    protected void afterAdd(Node<E> node) {
        // 找到失衡节点 parent.parent.parent.null;
//        while ((node = node.parent) != null) {
//            if (this.isBalanced(node)) { // 是否平衡
//                // 更新高度
//                this.updateHeight(node);
//            } else {
//                // 恢复平衡
//                this.rebalance(node);
//                break;// 只要不平衡的节点恢复上面就恢复了
//            }
//        }
//        // 说明添加节点之后还是平衡的
//        return;
    }

    /**
     * 删除节点之后的调整
     *
     * @param node 被删除的节点
     */
    @Override
    protected void afterRemove(Node<E> node) {
        while ((node = node.parent) != null) {
            if (this.isBalanced(node)) { // 是否平衡
                // 更新高度
                this.updateHeight(node);
            } else {
                // 恢复平衡
                this.rebalance(node); // 删除的话在修复之后祖父节点还有可能失衡
            }
        }
        // 说明添加节点之后还是平衡的
        return;
    }

    private void toAVL(Node<E> node) {
        // 找到失衡节点 parent.parent.parent.null;
        while ((node = node.parent) != null) {
            if (this.isBalanced(node)) { // 是否平衡
                // 更新高度
                this.updateHeight(node);
            } else {
                // 恢复平衡
                this.rebalance(node);
                break;// 只要不平衡的节点恢复上面就恢复了
            }
        }
        // 说明添加节点之后还是平衡的
        return;
    }

    public void toAVL() {
        if (this.root == null) {
            return;
        }
        Queue<Node<E>> queue = new LinkedList<Node<E>>();
        queue.offer(this.root);
        while (!queue.isEmpty()) {
            Node<E> node = queue.poll();
            toAVL(node);
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
    }


    @Override
    protected Node<E> createNode(E element, Node<E> parent) {
        return new AVLNode<>(element, parent); // 因为AVLNode跟Node相比多了一个height
    }


    /**
     * 恢复平衡
     *
     * @param grand 高度最低的那个不平衡祖父节点
     */
    private void rebalance2(Node<E> grand) {
//        AVLNode<E> valGrand = (AVLNode<E>) grand;
        // 找到左右子节点的较高节点
        Node<E> parent = ((AVLNode<E>) grand).tallerChild();
        Node<E> node = ((AVLNode<E>) parent).tallerChild();

        if (parent.isLeftChild()) {// L
            if (node.isLeftChild()) {  // L
                // 现实是LL的情况,
                // 对g进行右旋转，
                this.rotateRight(grand);
            } else { // R
                // 现在是LR的情况
                // 对p进行左旋转， 变成LL
                this.rotateLeft(parent);
                // 对g进行右旋转，
                this.rotateRight(grand);

            }
        } else { // R
            if (node.isLeftChild()) { // L
                // 现在是RL的情况
                // 对p进行右旋转, RR
                this.rotateRight(parent);
                // 对g进行左旋转, 变成RR
                this.rotateLeft(grand);
            } else { // R
                // 现在是RR的情况
                // 对g进行右旋转，
                this.rotateLeft(grand);
            }
        }

    }


    /**
     * 恢复平衡， 不使用旋转，使用一种统一的形式恢复平衡， 从左到右递增，对称构建树
     *
     * @param grand 高度最低的那个不平衡祖父节点
     */
    private void rebalance(Node<E> grand) {
        // AVLNode<E> valGrand = (AVLNode<E>) grand;
        // 找到左右子节点的较高节点
        Node<E> parent = ((AVLNode<E>) grand).tallerChild();
        Node<E> node = ((AVLNode<E>) parent).tallerChild();

        if (parent.isLeftChild()) {// L
            if (node.isLeftChild()) {  // L
                this.rotate(grand, node.left, node, node.right, parent, parent.right, grand, grand.right);
            } else { // R
                this.rotate(grand, parent.left, parent, node.left, node, node.right, grand, grand.right);
            }
        } else { // R
            if (node.isLeftChild()) { // L
                this.rotate(grand, grand.left, grand, node.left, node, node.right, parent, parent.right);
            } else { // R
                this.rotate(grand, grand.left, grand, parent.left, parent, node.left, node, node.right);
            }
        }
    }


    private void rotate(
            Node<E> r, // 初始根节点
            Node<E> a, Node<E> b, Node<E> c,
            Node<E> d, // 变为根节点
            Node<E> e, Node<E> f, Node<E> g
    ) {
        d.parent = r.parent;
        if (r.isLeftChild()) {
            r.parent.left = d;
        } else if (r.isRighrChild()) {
            r.parent.right = d;
        } else {
            this.root = d;
            d.parent = null;
        }
        //  左子树a - b - c
        b.left = a;
        b.right = c;
        if (a != null) {
            a.parent = b;
        }
        if (c != null) {
            c.parent = b;
        }
        this.updateHeight(b);
        // 右子树 e - f - g
        f.left = e;
        f.right = g;
        if (e != null) {
            e.parent = f;
        }
        if (g != null) {
            g.parent = f;
        }
        this.updateHeight(f);
        // 中间   b - d - f
        d.left = b;
        d.right = f;
        if (b != null) {
            b.parent = d;
        }
        if (f != null) {
            f.parent = d;
        }
        this.updateHeight(d);
    }


    private void rotateLeft(Node<E> grand) {
        Node<E> parent = grand.right;
        Node<E> child = parent.left;

        grand.right = child;
        parent.left = grand;
        this.afterRotate(grand, parent, child);
    }

    private void rotateRight(Node<E> grand) {
        Node<E> parent = grand.left;
        Node<E> child = parent.right;

        grand.left = child;
        parent.right = grand;

        // 维护parent和更新高度
        this.afterRotate(grand, parent, child);
    }

    /**
     * 维护parent和更新高度
     *
     * @param grand
     * @param parent
     * @param child
     */
    private void afterRotate(Node<E> grand, Node<E> parent, Node<E> child) {
        // 更新维护一下parent 的 parent ,
        parent.parent = grand.parent;
        if (grand.isLeftChild()) {// 更新一下 grand.parent的子节点
            grand.parent.left = parent;
        } else if (grand.isRighrChild()) {
            grand.parent.right = parent;
        } else { // top是根节点
            this.root = parent;
            parent.parent = null;
        }
        // 更新 child的parent
        if (child != null) {
            child.parent = grand;
        }
        // 更新grand 的 parent
        grand.parent = parent;

        // 更新高度
        this.updateHeight(grand);
        this.updateHeight(parent);
    }


    protected void updateHeight(Node<E> node) {
        ((AVLNode<E>) node).updateHeight();
    }

    private boolean isBalanced(Node<E> node) {
        return Math.abs(((AVLNode<E>) node).balanceFactor()) <= 1;
    }

    private static class AVLNode<E> extends Node<E> {

        public AVLNode(E element, Node<E> parent) {
            super(element, parent);
        }

        int height = 1;

        public int balanceFactor() { // 计算平衡因子
            // 左子树的高度减去
            int leftHeight = this.left == null ? 0 : ((AVLNode<E>) this.left).height; // 默认的Node没有height属性
            int rightHeight = this.right == null ? 0 : ((AVLNode<E>) this.right).height; // 默认的Node没有height属性
            return leftHeight - rightHeight;
        }

        public void updateHeight() {
            // 左子树的高度减去
            int leftHeight = this.left == null ? 0 : ((AVLNode<E>) this.left).height; // 默认的Node没有height属性
            int rightHeight = this.right == null ? 0 : ((AVLNode<E>) this.right).height; // 默认的Node没有height属性
            this.height = 1 + Math.max(leftHeight, rightHeight); // 自己的高度就是左右节点高度较高的那一个
        }

        public Node<E> tallerChild() {
            // 左子树的高度减去
            int leftHeight = this.left == null ? 0 : ((AVLNode<E>) this.left).height; // 默认的Node没有height属性
            int rightHeight = this.right == null ? 0 : ((AVLNode<E>) this.right).height; // 默认的Node没有height属性
            if (leftHeight > rightHeight) return this.left;
            if (leftHeight < rightHeight) return this.right;
            return this.isLeftChild() ? this.left : this.right;
            // 同高度返回相同方向
//            if ()


        }
    }
}
